#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

class Solution{
    private:
    struct mytype{
        int u;
        int v;
        
        bool operator>(const mytype& other) const{
            return u+v > other.u+other.v;
        }
        bool operator<(const mytype& other) const{
            return u+v < other.u+other.v;
        }
    };
    priority_queue<mytype, vector<mytype>, greater<mytype>> minHeap;
    priority_queue<mytype, vector<mytype>, less<mytype>> maxHeap;

    public:
    //out of memory
    vector<vector<int>> ans1(vector<int>& nums1, vector<int>& nums2, int k){
        int m = nums1.size(), n = nums2.size();
        for(int i = 0; i != m; i++){
            for(int j = 0; j != n; j++){
                if(minHeap.size() <= k){
                    minHeap.push({nums1[i], nums2[j]});
                }
            }
        }
        vector<vector<int>> ret;
        for(int i = 0; i != k; i++){
            vector<int> temp;
            temp.push_back(minHeap.top().u);
            temp.push_back(minHeap.top().v);
            ret.push_back(temp);
            minHeap.pop();
        }
        
        return ret;
    }

    vector<vector<int>> ans2(vector<int>& nums1, vector<int>& nums2, int k){
        auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };

        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> ans;   
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < min(k, m); i++) {
            pq.emplace(i, 0);
        }
        while (k-- > 0 && !pq.empty()) {
            auto [x, y] = pq.top(); 
            pq.pop();
            ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
            if (y + 1 < n) {
                pq.emplace(x, y + 1);
            }
        }

        return ans;
    }
};

void show(vector<vector<int>>& ret){
    int m = ret.size(), n = ret[0].size();
    for(int i = 0; i != m; i++){
        for(int j = 0; j != n; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << endl;
    }
}

void test(){
    Solution s;
    vector<int> nums1 = {1,7,11}, nums2 = {2,4,6};
    int k = 3;

    vector<vector<int>> ret = s.ans2(nums1, nums2, k);
    show(ret);
}

int main(void){
    test();

    return 0;
}